1. Field of the Invention (Technical Field)
The present invention relates to a method and apparatus for automatically planning movements of robot manipulators through a cluttered environment, the invention finding a collision-free path, if one exists, from any starting configuration of the manipulator to any desired ending configuration.
2. Background Art
Robotic systems require motion planning components so that manipulators may execute tasks without colliding with objects in their workspace. Motion planning components must find a short and collision-free path from any starting point to any goal position of a manipulator. In the prior art, manipulators are either controlled directly by human operators or restricted to trajectories that have been pre-computed through hours or days of off-line computation and programming.
Human operators have significant drawbacks. They require a long training period before becoming comfortable with and proficient at the use of robot manipulators. While human operators can react creatively to changing circumstances, they become fatigued and otherwise prone to error and reduced efficiency. Most importantly, when robotic operations are performed in hazardous environments, such as in hard vacuum, under high water pressure, and in high radiation zones, use of human workers becomes extremely expensive if not impossible. Safety and tele-operations equipment are costly and reduce the efficiency of operations.
Robot manipulator trajectories may be generated through off-line programming from descriptions of the robotic tasks and the workspace environment. However, such trajectories are prone to becoming invalid due to unexpected changes of position of objects in the environment or the introduction of new objects into the environment. The trajectories cannot be modified without halting operations. Hence, off-line programming is only feasible in a highly structured and well-controlled environment such as a manufacturing plant.
No practical real-time motion planners exist in the prior art. The prior art planners may be broadly placed into two categories: complete and heuristic. Complete motion planners either find a collision-free path if one exists or show that not one exists. These planners require long computation times, on the order of tens of hours. Heuristic motion planners are relatively fast for many problems (under ten minutes), but may fail to find existing collision-free paths.
At least three complete motion planners exist in the prior art, all requiring long computation times, on the order of several hours for five and six-degree-of-freedom (DOF) robot manipulators. M. S. Branicky and W. S. Newman, "Rapid Computation of Configuration Obstacles," 1990 Proceedings of IEEE International Conference on Robotics and Automation, pp. 304-10; B. Paden, et al., "Path Planning Using a Jacobjan-Based Freespace Generation Algorithm," 1989 Proceedings of IEEE International Conference on Robotics and Automation, pp. 1732-37; and T. Lozano-Perez, "A Simple Motion-Planning Algorithm for General Robot Manipulators," IEEE Journal of Robotics and Automation, Vol. RA-3, No. 3, pp. 224-38, June 1987. The Lozano-Perez motion planner is commercially available as a part of the robot simulation package Cimstation, available from Silma, Inc. Fast computation times are vital for five and six DOF robots because those are the most common types of robot manipulators in day-to-day use. A six DOF robot manipulator is required to position (x, y, z) and orient (roll, pitch, yaw) an object anywhere within the robot's workspace.
Heuristic motion planners existing in the prior art include J. Barraquand and J. Latombe, "A Monte-Carlo Algorithm for Path Planning With Many Degrees of Freedom," 1990 Proceedings of IEEE International Conference on Robotics and Automation, pp. 1712-17, and B. Faverjon and P. Tournassoud, "A Local Approach for Path Planning of Manipulators with a High Number of Degrees of Freedom," 1987 Proceedings of IEEE International Conference on Robotics and Automation, pp. 1152-59. While these heuristic motion planners have average computation times under ten minutes for five and six DOF problems, all are incomplete in that they can fail to find a collision-free motion for some problems for which one exists.
Real-time automation of motion planning that also finds a collision-free path if one exists offers a number of advantages over the prior art. It relieves human workers of the continual burden of detailed motion design and collision avoidance, and allows them to concentrate on the robotic tasks at a supervisory level. Robots with an automatic motion planner can accomplish tasks with fewer, higher-level commands. Robotic tele-operations can become much more efficient because commands can be given at coarser time intervals. With an automatic motion planner and appropriate environment sensing systems, robots can adapt quickly to unexpected changes in the environment and be tolerant to modeling errors of the workspace.
An effective motion planning method and device, in order to be used in real-life production and research tasks, must be able to plan a collision-free motion for a six DOF robot manipulator within a few minutes on today's computer workstations. It must also be robust in that it succeeds in finding a motion in most realistic environments. With the rapidly increasing speed and decreasing cost of computer workstations, the method and device of the present invention will plan motions in seconds rather than minutes.